Search results for "Target expression"

Learning a class of regular expressions via restricted subset queries

1992

A wide class of regular expressions non-representable as unions of “smaller” expressions is shown to be polynomial-time learnable via restricted subset queries from arbitrary representative examples “reflecting” the loop structure and a way the input example is obtained from the unknown expression. The corresponding subclass of regular expressions of loop depth at most 1 is shown to be learnable from representative examples via membership queries. A wide class of expressions with loops A+ of arbitrary loop depth is shown to be learnable via restricted subset queries from arbitrary examples.